12.3. Grafların Bellek Üzerinde Tutulması

Grafların bellekte tutulması veya gösterilmesi ile ilgili birçok yöntem vardır. Bunlardan birisi, belki de en yalın olanı, doğrudan matris şeklinde tutmaktır; grafın komşuluk veya bitişiklik matrisi elde edilmişse, bu matrisler doğrudan programlama dilinin matris bildirim özellikleri uyarınca bildirilip kullanılabilir. Ancak grafın durumu ve uygulamanın gereksinimine göre diğer yöntemler daha iyi sonuç verebilir. Bir grafın bellekte tutulması için, temelde, dört farklı yöntem biri kullanılabilir:

İlki matris üzerinde grafın komşuluk veya bitişiklik matrisi doğrudan matris değişken üzerinde tutulur. İkinci yöntem ise iki-dizi kullanılmasıdır; dizinin biri grafın tüm kenar bilgilerini liste şeklinde tutarken, ikinci dizi birinci dizide tutulan kenarların hangi düğümlere ait olduğunu işaret eder. Üçüncü yöntem ise, bağlantılı liste (link list) kullanılmasıdır; bu yöntemde, düğümler arasındaki bağlantı, doğrudan, düğüm veri yapısı içerisindeki alanlarda tutulur. Dördüncü yöntem olarak dizili-bağlantılı liste kullanılabilir; burada, düğümler vektör üzerinde tutulur ve düğümlere olan bağlantı, bağlantılı liste şeklinde vektörün üzerindeki ilgili düğümüne bağlanır; vektörlü-bağlantılı liste, dizili-bağlantı liste olarakta anılır.